﻿#include <iostream>
#include <vector>

using namespace std;

#define MIN(a, b) (a < b ? a : b)
#define INVALID_VALUE 0x1fffffff
#define LIKE_ADD 2
#define GIFT_MUL 2
#define CHAT_MINUS 2

static int recur(const int likeCost, const int giftCost, const int privateChatCost, const int start, const int end, int cur, int curCost)
{
	// 达到目标人气
	if (cur == end)
	{
		return 0;
	}

	// 目标人气不能超过初始人气差的2倍
	if (cur > start + (end - start) * 2)
	{
		return INVALID_VALUE;
	}

	// 总花费不能超过以最慢的方式增加的花费
	// start + LIKE_ADD * n = end
	// total cost = n * likeCost
	if (curCost > (end - start) / LIKE_ADD * likeCost)
	{
		return INVALID_VALUE;
	}

	// 点赞
	int a = likeCost + recur(likeCost, giftCost, privateChatCost, start, end, cur + LIKE_ADD, curCost + likeCost);

	// 送礼
	int b = giftCost + recur(likeCost, giftCost, privateChatCost, start, end, cur * GIFT_MUL, curCost + giftCost);

	// 私聊
	int c = privateChatCost + recur(likeCost, giftCost, privateChatCost, start, end, cur - CHAT_MINUS, curCost + privateChatCost);

	return MIN(MIN(a, b), b);
}

static int byStrictTable(const int likeCost, const int giftCost, const int privateChatCost, const int start, const int end)
{
	int targetSize = start + (end - start) * 2 + 1;
	int costSize = (end - start) / LIKE_ADD * likeCost + 1;
	int* dp = (int*)malloc(costSize * targetSize * sizeof(int));
	memset(dp, 0, costSize * targetSize * sizeof(int));

	// dp[cur, curCost] = dp[curCost + cur * costSize]
	for (int cur = 0; cur < targetSize; cur++)
	{
		for (int curCost = 0; curCost < costSize; curCost++)
		{
			dp[curCost + cur * costSize] = INVALID_VALUE;
		}
	}

	for (int curCost = 0; curCost < costSize; curCost++)
	{
		dp[curCost + end * costSize] = 0;
	}

	for (int cur = targetSize - 1; cur >= 0; --cur)
	{
		if (cur == end) continue;

		for (int curCost = costSize - 1; curCost >= 0; --curCost)
		{
			// 点赞
			int a = INVALID_VALUE;
			if (cur + LIKE_ADD < targetSize && curCost + likeCost < costSize)
				a = likeCost + dp[curCost + likeCost + (cur + LIKE_ADD) * costSize];

			// 送礼
			int b = INVALID_VALUE;
			if (cur * GIFT_MUL < targetSize && curCost + giftCost < costSize)
				b = giftCost + dp[curCost + giftCost + (cur * GIFT_MUL) * costSize];

			// 私聊
			int c = INVALID_VALUE;
			if (cur - CHAT_MINUS >= 0 && curCost + privateChatCost < costSize)
				c = privateChatCost + dp[curCost + privateChatCost + (cur - CHAT_MINUS) * costSize];

			dp[curCost + cur * costSize] = MIN(a, MIN(b, c));
		}
	}

	int res = dp[start * costSize];
	free(dp);
	return res;
}

static int minCoins(const char* input)
{
	// 点赞
	int likeCost = 0;
	// 送礼
	int giftCost = 0;
	// 私聊
	int privateChatCost = 0;
	int start = 0;
	int end = 0;
	
	int index = 0;
	int firstNotSpace = 0;
	int strLen = strlen(input);
	vector<char*> arr;
	while (index < strLen)
	{
		if (input[index] == ' ' && index > firstNotSpace)
		{
			char* tmp = (char*)malloc(index - firstNotSpace + 1);
			memset(tmp, 0, index - firstNotSpace + 1);
			memcpy(tmp, input + firstNotSpace, index - firstNotSpace);
			arr.push_back(tmp);
			firstNotSpace = index + 1;
		}

		++index;
	}

	char* tmp = (char*)malloc(index - firstNotSpace + 1);
	memset(tmp, 0, index - firstNotSpace + 1);
	memcpy(tmp, input + firstNotSpace, index - firstNotSpace);
	arr.push_back(tmp);

	index = 0;
	for (auto it = arr.begin(); it != arr.end(); it++)
	{
		char* numStr = *it;
		switch (index)
		{
		case 0:
			sscanf_s(numStr, "%d", &likeCost);
			break;

		case 1:
			sscanf_s(numStr, "%d", &giftCost);
			break;

		case 2:
			sscanf_s(numStr, "%d", &privateChatCost);
			break;

		case 3:
			sscanf_s(numStr, "%d", &start);
			break;

		case 4:
			sscanf_s(numStr, "%d", &end);
			break;

		default:
			break;
		}

		++index;
		free(*it);
	}

	int minCost = recur(likeCost, giftCost, privateChatCost, start, end, start, 0);
	printf("%d\n", minCost);
	minCost = byStrictTable(likeCost, giftCost, privateChatCost, start, end);
	printf("%d\n", minCost);
	return minCost;
}

// CC里面有一个土豪很喜欢一位女直播Kiki唱歌，平时就经常给她点赞、送礼、私聊。最近CC直播平台在举行中秋之星主播唱歌比赛，假设一开始该女主播的初始
// 人气值为start，能够晋升下一轮人气需要刚好达到end，土豪给主播增加人气的可以采取的方法有:
// a.点赞 花费xC币，人气 + 2
// b.送礼 花费yC币，人气 * 2
// c.私聊 花费zC币，人气 - 2
//
//其中end远大于start，且end为偶数，请写一个程序帮助土豪计算一下，最少花费多少C币能帮助该主播Kiki将人气刚好到达end，
// 从而能够晋级下一轮 ?
//
//	输入描述：
// 第一行输入5个数据，分别是 : x y z start end, 每项数据以空格分开。
// 其中，0 < x, y, z <= 10000, 0 < start, end <= 1000000
//
//	输出描述 :
//	需要花费的最少C币。
//
//	示例：
//	输入
//		3 100 1 2 6
//	输出
//		6
//
//思路：
// 动态规划，但是在写递归的过程中要注意，由于人气值是有可能下降的，如果按照常规方法尝试，会进入无限递归。故基础条件应该加更多的限制。
// 1. 按照每次增加人气最小的方式花费的C币数量，那么最优方案的C币数量不应该超过这个值。
// 2. 由于人气是可能超过目标值的，故超过之后，需要通过c方案减人气值，在减人气值之前，最大的人气值不应该超过目标人气值的2倍。
int main_AchieveTargetPopularValueByLeastCost()
{
	char input[] = "3 100 1 10 20";
	minCoins(input);
	return 0;
}